The present disclosure relates to bitmap processing for log-structured data file stores.
Non-log-structured storage management systems, such as those used in association with hard disk and/or solid state drives, can prepare and send write requests to the drives. In some cases, such file systems can identify which blocks are free or allocated, determine in which blocks to write new data using bitmaps, and/or update data using an extents tree, for example, that informs the system about the logical block address (LBA) associated with the data.
FIG. 3A is a diagram of an example bitmap 300 according to prior solutions. As shown, the bitmap uses a single bit to flag whether a given block in a data volume is free or used. Such bitmaps can provide adequate performance for various hard disk and solid state drive-based file systems (e.g., ext4, xfs, etc.), but have significant drawbacks in other types of file systems, such as log-structured file systems (LFSs) (e.g., F2FS, NILFS2, etc.) because they are unable to accommodate copy-on-write policies. For instance, in such log-structured file systems, if a data update needs to be performed, a new segment in a new physical location generally needs to be prepared for writing the data, which the above-described prior solutions are unable to efficiently accommodate.
Further, current LFSs generally do not use bitmaps in the above, historical manner to track logical blocks, because they are unable to account for additional states (e.g., pre-allocated, valid/invalid, etc.), and cannot be used to track a block's lifecycle inside an LFS volume. For instance, in the case of an erase block failure in an LFS, the above bitmap-based approach is unable to flag and overcome such failures. Instead, LFSs use alternative tracking approaches (e.g., dedicated tables, etc.) that increase overhead and exhibit lower performance.